import functools


class Solution(object):
    def cutOffTree(self, forest):
        """
        :type forest: List[List[int]]
        :rtype: int
        """
        m = len(forest)
        n = len(forest[0])
        stack = []
        for i in range(m):
            for j in range(n):
                if forest[i][j] > 1:
                    stack.append([forest[i][j], i, j])
        stack.sort()
        if not stack:
            return 0
        stack.insert(0, [forest[0][0], 0, 0])

        def search(start, end):
            if start == end:
                return 0
            used = [[0 for _ in range(n)] for _ in range(m)]
            used[start[0]][start[1]] = 1
            count = 0
            now = {start}
            while now:
                next_set = set()
                count += 1
                for x, y in now:
                    for ux, uy in [(x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)]:
                        if 0 <= ux < m and 0 <= uy < n and forest[ux][uy] >= 1 and used[ux][uy] == 0:
                            if (ux, uy) == end:
                                return count
                            next_set.add((ux, uy))
                            used[ux][uy] = 1
                now = next_set
            return -1

        count = 0
        for i in range(1, len(stack)):
            val = search((stack[i - 1][1], stack[i - 1][2]), (stack[i][1], stack[i][2]))
            if val >= 0:
                count += val
            else:
                return - 1
        return count


data = Solution()
forest = [[8, 11, 4, 13], [16, 10, 12, 14], [1, 19, 18, 20], [15, 3, 6, 7], [17, 2, 5, 9]]
print(data.cutOffTree(forest))
forest = [[1, 3], [4, 2]]
print(data.cutOffTree(forest))
